#pragma once
#include<iostream>
#include<vector>
using namespace std;
//所谓位图，就是用每一位来存放某种状态，
// 适用于海量数据，数据无重复的场景。通常是用 
//来判断某个数据存不存在的。

namespace sbt
{
	//非类型模板参数
	template<size_t N>//N指需要多少比特位
	class bitset
	{
	public:
		//构造函数
		bitset()
		{
			_bits.resize(N / 32 + 1, 0);
		}

		//插入
		void set(size_t x)
		{
			//计算在第几个整型
			size_t i = x / 32;
			//计算在这个整型的第几位上
			size_t j = x % 32;
			//左移是指向高位移，不管大端小端
			_bits[i] |= (1 << j);//这样第j位比特位就是1，按位或|就可以
			//将该位置1且不影响其他位
		}
		//删除
		void reset(size_t x)
		{
			//计算在第几个整型
			size_t i = x / 32;
			//计算在这个整型的第几位上
			size_t j = x % 32;

			_bits[i] &= ~(1 << j);//第j位比特位是0，按位与&
			//将该位置置0且不影响其他位
		}
		//检测在不在
		bool test(size_t x)
		{
			//计算在第几个整型
			size_t i = x / 32;
			//计算在这个整型的第几位上
			size_t j = x % 32;

			return _bits[i] & (1 << j);//非零则在，真
			//零则不在，假
		}
	private:
		vector<int> _bits;
	};


	template<size_t N>
	class twobitset//两位比特位表示一种状态
	{				//用两个位图共同控制
	public:
		//插入
		void set(size_t x)
		{
			//00->01
			//01->10
			//10->10//不变，出现两次几以上
			if (_bs1.test(x) == false && _bs2.test(x) == false)
			{//00->01
				_bs2.set(x);
			}
			else if (_bs1.test(x) == false && _bs2.test(x) == true)
			{//01->10
				_bs1.set(x);
				_bs2.reset(x);
			}

		}

		void PrintOnce()//出现一次的打印
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bs1.test(i) == false && _bs2.test(i) == true)
				{
					cout << i << endl;
				}
			}
		}

	private:
		bitset<N> _bs1;
		bitset<N> _bs2;

	};



	template<size_t N>
	class twobitset2//两位比特位表示一种状态
	{				//用两个位图共同控制
	public:
		//插入
		void set(size_t x)
		{
			//00->01
			//01->10
			//10->11
			//11
			if (_bs1.test(x) == false && _bs2.test(x) == false)
			{//00->01
				_bs2.set(x);
			}
			else if (_bs1.test(x) == false && _bs2.test(x) == true)
			{//01->10
				_bs1.set(x);
				_bs2.reset(x);
			}
			else if (_bs1.test(x) == true && _bs2.test(x) == false)
			{
				_bs1.set(x);
				_bs2.set(x);
			}

		}

		void PrintLowerTwice()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bs1.test(i) == false && _bs2.test(i) == true
					|| _bs1.test(i) == false && _bs2.test(i) == true
					|| _bs1.test(i) == true && _bs2.test(i) == false)
				{
					cout << i << endl;
				}
			}
		}

	private:
		bitset<N> _bs1;
		bitset<N> _bs2;

	};
}